package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversal {
TreeNode fake = new TreeNode(0);
    
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        
        if (root != null) {
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            queue.offer(root);
            queue.offer(fake);
            
            TreeNode current;
            ArrayList<Integer> clvl = new ArrayList<Integer>();
            while((current = queue.poll()) != null){
                if (current == fake){
                    res.add(clvl);
                    clvl = new ArrayList<Integer>();
                    if (queue.peek() != null)
                        queue.offer(fake);
                } else {
                    clvl.add(current.val);
                    if (current.left != null)
                        queue.offer(current.left);
                    if (current.right != null)
                        queue.offer(current.right);
                    
                }
            }
        }
        
        return res;
    }
}
